package my.topcoder.practice.srm435;

/**
 * Algorithm competition: TopCoder SRM 435 DIV1 250
 * <p>
 * 
 * In biology, organisms have the following property: Starting from the first
 * cell (the zygote), each cell during an organism's development process either
 * divides into 2 other cells or does not divide at all. An organism is mature
 * when all of its cells will not divide any further. Let's assign a unique
 * number to each cell in an organism's development process. For example,
 * consider a species in which each organism starts with cell 0, which divides
 * into cells 1 and 2. Cell 1 divides into cells 3 and 4. Cells 2, 3 and 4 do
 * not divide. Every mature organism of this species will consist of exactly 3
 * cells - 2, 3 and 4. During the development process, if we kill a cell, it
 * will be absent in the mature form of the organism. If that cell happens to be
 * a cell that divides, then the mature organism will be missing all of the
 * cell's descendants as well because the cell is killed before it has a chance
 * to divide. For example, in the organism described above, if we kill cell 1
 * during the development process, the mature organism will contain only cell 2.
 * <p>
 * 
 * Example:
 * <p>
 * {-1,0,0,2,2,4,4,6,6}<br>
 * 4<br>
 * Returns: 2<br>
 * <p>
 * 
 * @author meijunyuan
 * 
 */
public class CellRemoval {
	/**
	 * 
	 * @param parentCell
	 *            parentCell describing the development process of an organism.
	 *            The i-th element of parentCell is the parent cell of cell i
	 *            (where i is a 0-based index). The zygote's parent is -1.
	 *            parentCell will contain exactly N elements, where N is an odd
	 *            integer between 1 and 50, inclusive. There will be exactly one
	 *            "-1" element in parentCell. Every element of parentCell will
	 *            be between -1 and N-1, inclusive. parentCell will form a
	 *            binary tree.
	 * @param deletedCell
	 *            deletedCell will be between 0 and N-1, inclusive.
	 * @return the number of cells the mature form of this organism would have
	 *         if you killed cell deletedCell during the development process.
	 */
	public int cellsLeft(int[] parentCell, int deletedCell) {
		int l = parentCell.length;
		int[] marks = new int[l];
		int numOfCell = 0;
		for (int i = 0; i < l; i++) {
			mark(i, false, parentCell, deletedCell, marks);
		}
		for (int j = 0; j < l; j++) {
			if (marks[j] == 0) {
				numOfCell++;
			}
		}
		return numOfCell;
	}

	private void mark(int i, boolean called, int[] parentCell, int deletedCell,
			int[] marks) {
		if (marks[i] == 0) {
			if (called) {
				// mark as parent
				marks[i] = 1;
			}
			if (parentCell[i] != -1) {
				mark(parentCell[i], true, parentCell, deletedCell, marks);
				if (marks[parentCell[i]] == 2) {
					// mark as deleted
					marks[i] = 2;
				}
			}
			if (i == deletedCell) {
				// mark as deleted
				marks[i] = 2;
			}
		}
	}

	public static void main(String[] args) {
		CellRemoval cellRemoval = new CellRemoval();
		System.out.println(cellRemoval.cellsLeft(new int[] {-1,0,0,1,1}, 2));
	}
}
